package com.base.leetcode;

import java.util.Arrays;

/**
 * @Author: hdhao
 * @Create: 2023/4/5 - 11:22
 * @Version: v1.0
 */
//小顶堆
public class MinHeap {
    int[] array;
    int size;
    public MinHeap(int capacity){
        array = new int[capacity];
    }
    public MinHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }
    public boolean isFull() {
        return size == array.length;
    }
    //获取堆顶元素
    public int peek(){
        return array[0];
    }

    //删除堆顶元素
    public int poll(){
        int top = array[0];
        //与最后的元素交换
        swap(0,size - 1);
        size--;
        down(0);
        return top;
    }

    //删除指定索引处的元素
    public int poll(int index) {
        //待删除元素
        int deleted = array[index];
        swap(index,size - 1);
        size--;
        down(index);
        return deleted;
    }

    //替换堆顶的元素
    public void replace(int replace) {
        array[0] = replace;
        down(0);
    }
    //堆的尾部添加元素
    public boolean offer(int offered) {
        if (size == array.length) {
            return false;
        }
        up(offered);
        size++;
        return true;
    }

    public void up(int offered) {
        int child = size;
        while (child > 0) {
            int parent = (child - 1) / 2;
            if (offered < array[parent]) {
                array[child] = array[parent];
            }else {
                break;
            }
            child = parent;
        }
        array[child] = offered;
    }
    //建堆
    private void heapify(){
        //如何找到最后这个非叶子节点 size/2 -1
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i);
        }
    }

    //将parent索引处的元素下潜，与两个孩子较大者交换，直至没有孩子或者孩子没它大
    private void down(int parent) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int min = parent;
        if (left < size && array[left] < array[min]) {
            min = left;
        }
        if (right < size && array[right] < array[min]) {
            min = right;
        }
        if (min != parent) {
            swap(min,parent);
            down(min);
        }

    }

    private void swap(int max, int parent) {
        int t = array[max];
        array[max] = array[parent];
        array[parent] = t;
    }

    public static void main(String[] args) {
//        int[] array = {1,2,3,4,5,6,7};
//        MaxHeap maxHeap = new MaxHeap(array);
//        System.out.println(Arrays.toString(maxHeap.array));
        //堆排序
        int[] array = {2, 3, 1, 7, 6, 4, 5};
        MinHeap heap = new MinHeap(array);
        System.out.println(Arrays.toString(heap.array));
        while (heap.size > 1) {
            //将堆顶元素交换到堆底
            heap.swap(0, heap.size - 1);
            heap.size--;
            //交换完之后，调整剩余元素的位置，使其重新符合大顶堆的定义
            //(让0索引处的元素下潜)
            heap.down(0);
        }
        System.out.println(Arrays.toString(heap.array));
    }
}
